\chapter{Disponibilità e Ridondanza}
In un sistema distribuito è molto importante avere una distribuzione ragionevole
dei file, in modo tale da ottimizzare le operazioni di lettura e scrittura.\\
Si parla di {\bf disponibilità} riferendosi alla possibilità associata ad un
file di essere disponibile su di un server, mentre la {\bf Ridondanza} è il
numero di duplicati che sono presenti all'interno della rete.\\ \\
Definiamo:\\ \\
$\gamma$ come la possibilità di guasto di un server\\{\bf $D_{r}$} come la
disponibilità in lettura\\ E analogamente {\bf $D_{w}$ } per la disponibilità in
scrittura.
\begin{itemize}
\item Una sola copia:  $D_{r} =  D_{w} =  1- \gamma$ ;
\item Due copie: $D_{r} = (1-\gamma)^2 + 2  \gamma  (1 -\gamma)$, ovvero la
probabilità che entrambi i server non siano guasti più quella che solo uno dei due
sia guasto. Con $\gamma = 1$ oppure $ \gamma = 0 $ si ha la stessa
disponibilità che con una copia, altrimenti con due copie la disponibilità è maggiore. 
Nel caso di scrittura invece la probabilità diminuisce perché per scrivere bisogna avere accesso a tutte le copie.
\item Con l'aumentare delle copie si segue lo stesso andamento, aumentando la
disponibilità per la lettura rendendo però inaccettabile la disponibilità in
scrittura, per il problema del {\bf Read One - Write All}.
\end{itemize}

In un ambiente di tipo File Sharing l'aumento delle copie del file risulta
essere un approccio utile, perché i file sono statici e quindi non devono essere
aggiornati, quindi avendo a disposizione un alto numero di peer, anche se di basta
qualità, si ottiene così un'alta disponibilità.
\section{Sistema RAID}

In un {\bf sistema RAID (Redundant Array of Independent Disk)} si aumenta il
livello di disponibilità inserendo delle informazioni ridondanti a livello
hardware. \\ Esistono diversi sistemi RAID, tra cui RAID-5.\\
\subsection {RAID-5}
RAID 5 utilizza la tecnica dei bit di parità, ovvero applicando la funzione XOR
tra due bit.\\
Una delle varianti è la tecnica {\bf Due su Tre}, ovvero presi a e b si applica
a XOR b = p, quindi uno dei dati è ridondante, infatti se si perde una delle
informazioni  è possibile comunque risalire a quella mancante effettuando
nuovamente lo XOR tra quelle ancora disponibili, per esempio se venisse a
mancare b, a XOR p = b.\\
Questa particolarità incide sulla disponibilità della risorsa in fase di lettura
e scrittura, infatti:
\begin {itemize}
\item  $D_{r} = (1 - \gamma)^3 - 3 \gamma (1 - \gamma) ^2$,  che coincide con il
caso senza ridondanza se $\gamma = 1 , 1/2, 0 $ ma differisce in tutti gli altri
punti, risulterà maggiore al sopra 1/2 e minore al di sotto, con una ridondanza
di 1.5.\\
Con un livello qualitativo alto dei peer allora è conveniente utilizzare questo
sistema, al contrario con una probabilità di guasto superiore a 1/2 il risultato
non è soddisfacente.
\item Vale analogamente per la $D_{w}, però se \gamma < 1/2 $  allora la
soluzione è più efficiente che avere una seconda copia del file.
\end{itemize}
In generale però non ha molto senso lavorare a livello di bit, quindi si
preferisce una soluzione {\bf K su N}, ovviamente $k < n$, per poter quindi
lavorare su sequenze di bit.
Considerando per esempio un sistema 3 su 5 non si può più usare lo XOR per
ritrovare l'informazione persa, questo perché è molto importante anche la
posizione dei bit all'interno della sequenza, quindi serve una funzione non
commutativa e di solito si utilizza l'algebra lineare.\\\\
Preso un vettore di bit  [b1, b2, b3] lo si moltiplica per una matrice di
codifica ottenendo così un vettore di 5 elementi. In questo modo sarà possibile,
dato un sottoinsieme di tre elementi del risultato, risalire ai 3 bit di
partenza nel caso in cui la matrice di codifica risulta essere invertibile.\\
Nel Codice Sistematico si costruisce la matrice di codifica dividendola in due
parti, la matrice identità e un matrice scelta in modo da mantenere l'invertibilità.\\
Questa soluzione risulta essere più costosa di quella con il bit di parità,
sopratutto perché le colonne che non fanno parte della matrice Identità hanno
bisogno di un numero di bit maggiore di 1 per essere codificate, quindi la
ridondanza sarà maggiore di due.


\section {Erasure Code}
Gli {\bf Erasure Code} trasformano un messaggio formato da k simboli in uno
di lunghezza maggiore, n, in modo tale che avendo ricevuto n simboli sia
possibile recuperare il messaggio anche se parti di questo sono andate perse.

\subsection {Campi di Galois}
{\bf I Campi di Galois} sono delle operazioni che vengono effettuate in modulo
numero primo p, non c'è quindi overflow perché il risultato è sempre compreso
tra 0 e p -1.\\
Per ovviare a problemi di rappresentazione solitamente si usano i Campi Estesi
di Galois. Per esempio consideriamo un campo esteso $ GF(2^{3})$ e il polinomio generatore
$\alpha=x^{3} + x + 1 $ la cui rappresentazione in bit è data dalla stringa 1 0
1 1  .\\
\begin{center}
\begin{tabular}{ | l | l | }
\hline
$\alpha ^0= 1$ & 001 \\ \hline
$\alpha ^ 1= x $ & 010  \\  \hline
$\alpha ^ 2= x^2 $ & 100  \\  \hline
$\alpha ^ 3= x +1  $ & 011  \\  \hline
$\alpha ^ 4= x^2 + x $ & 110  \\  \hline
$\alpha ^ 5=  x^2 + x +1 $ & 111  \\  \hline
$\alpha ^ 6= x^2 +1 $ & 101  \\  \hline
$\alpha ^ 7= 1 $ & 001  \\  \hline
\end{tabular}
\end{center}
Nel caso in cui $\alpha $ abbia grado uguale a quello del polinomio generatore,
allora lo si sottrae al polinomio , ottenendo così una rappresentazione con un
grado inferiore, se invece ha un grado superiore allora lo si scrive come
combinazione delle rappresentazioni dei polinomi avente grado inferiore per
esempio:  $\alpha ^ 4= (x+ 1) * x =x^2 + x $ = 110 .\\
\subsection {Complessità}
L'operazione XOR è molto semplice in quanto e realizzata a livello hardware con
un ciclo di clock.\\
Per il prodotto di polinomi invece  di polinomi in modulo p ha una complessità
maggiore che dipende dal numero di elementi non nulli dei polinomi, in generale
vengono eseguite le operazioni nel seguente ordine: moltiplicazione, XOR,
controllo di un eventuale overflow  e in caso positivo nuovamente uno XOR.\\\\
Aumentando il numero di bit a disposizione, cresce quindi la complessità. \\Si
può ottimizzare il tutto ottenendo una complessità costante aggiungendo una
tabella dei risultati ottenuti su cui poi fare una operazione di lookup in modo
tale che risulti poi  possibile calcolare
$ \alpha^i * \alpha^j = \alpha^{i+j}$.\\\\
In questo modo  aumentando i bit la complessità non aumenta ma aumenta la
memoria occupata.\\
Questa soluzione funziona correttamente e in un tempo ragionevole con valori
compresi 10 < k < 100.

\subsection{Metodo di Vandermonde}
In algebra lineare con {\bf matrice di Vandermonde} si indica una matrice le cui
righe (oppure le cui colonne) hanno elementi, a partire da 1, in progressione
geometrica, in modo tale che sia sempre verifica la condizione di invertibilità.

\subsection {Fountain Code}
I {\bf Codici a Fontana} scompongono una informazione  in k parti disgiunte,
detti pacchetti e poi ne inviano $ k+ \epsilon$ , con  $\epsilon $ abbastanza
grande  da poter ricostruire il messaggio originario.\\

\subsection {Random Linear Fountain }
I {\bf Random Linear Fountain } permettono di decodificare un file.
I pacchetti vengono scelti in maniera pseudo-casuale, viene generato un file
header che utilizzato come input da una funzione lineare genera una sequenza di
pacchetti su cui verrà effettuato lo XOR al fine di generare il pacchetto da
inviare. In questo modo due pacchetti inviati hanno 1 su $2^k$ possibilità di
essere identici.\\
Complessita:
Codifica : $k^2$, bisogna scandire k pacchetti e per ognuno effettuare k
operazioni.\\
Decodifica: viene eseguito uno XOR al contrario, il ricevente riceve il file
header che precedentemente era stato utilizzato per generare la sequenza dei
pacchetti su cui fare lo XOR , in questo modo è possibile risalire a quali
pacchetti sono utilizzati nella fase di codifica.

\subsection{Eliminazione di Gauss e Gauss Jordan}
L'eliminazione di {\bf Gauss Jordan }permette di risolvere sistemi lineari
utilizzando una matrice triangolare sia superiore che inferiore, la complessità
di questo algoritmo è di$ O(k^3)$.
Una volta ricevuti i k pacchetti ci sono due condizioni necessarie per far si
che la codifica sia possibile:
\begin{itemize}
\item L'elemento che si vuole decodificare è stato utilizzato almeno una volta.
\item Tutti i pacchetti ricevuti devono essere linearmente indipendenti tra di
loro. La probabilità per ogni pacchetto di essere combinazione di quelli
precedenti vale: (1-2$^k$) (1-2$^{-(k-1)}$ ... (1-1/8)(1-1/4)(1-1/2), per valori
di k molto grandi la probabilità vale all'incirca 29\%. 
\end{itemize}
Nel caso in cui non si riesca a decodificare il messaggio allora si deve
attendere l'invio di un ulteriore pacchetto. Con k = 10 e $\epsilon $ = 4 la
probabilità di decodifica vale 90\% e sale fino a 99\% con l'invio di 8
pacchetti ulteriori. Le probabilità rimangono lo stesse anche con k = 100 e
$\epsilon = 8$ , questo vuol dire che aumentando k diminuisce l'overhead, quindi
si approssima molto bene il comportamento di un sistema deterministico.\\
Data la complessità $O(k^3)$  dell'Eliminazione di Gauss Jordan è vantaggioso
utilizzare l'algoritmo con $10 < k <100$.\\

\subsection{Codice Luby Transform}
Il {\bf Codice LT} risolve il problema del Codice a Fontana con un algoritmo di
decodifica molto più semplice di quella di Gauss-Jordan implementata nei codici
a fontana e con una complessità inferiore cambiando anche il metodo statistico
con cui si decide se includere o meno un dato pacchetto nello XOR.\\
Faccio in modo che ogni tanto ci sia un pacchetto formato da una sola componente
(che quindi non è messo in XOR con nessuno), e lo uso per decodificare
parzialmente gli altri pacchetti che contengono la componente. In questo modo
avendo una componente già decodificata si riduce la dimensione dei pacchetti da
decodificare.\\
Se non arrivano pacchetti di dimensione 1 mi fermo finché non ne arriva almeno
uno.
La complessità di codifica nel caso pessimo vale $O(k^2)$, vale lo stesso
per l'operazione di decodifica. In realtà questa complessità dipende dalla
distribuzione di probabilità che uso.\\
Ideal soliton: $p(1)=\frac{1}{k}$ questo significa che in media mi aspetto di
trovare un pacchetto formato da una singola componente ogni k pacchetti
inviati.\\
In generale $\forall d \in [2,k]$ si ha $p(d)=\frac{1}{d(d-1)}$, questo fa
scendere la complessità da lineare a $O(k\log k)$ sia per la codifica che per la
decodifica.\\\\
Tutto questo funziona in teoria, ma nella pratica se si prova ad implementarlo
si vede che la probabilità di decodifica diminuisce al crescere del numero di
pacchetti. 
Questo succede perchè la statistica funziona bene studiando i grandi numeri, non
i piccoli, quindi abbiamo bisogno di qualcosa che tolleri bene l'incertezza
statistica.\\
Si introduce quindi il {\bf Robust Soliton}, in cui i parametri sono definiti
sperimentalmente per far funzionare l'algoritmo da un punto di vista pratico. 
In pratica aumentando p(1) riduco la probabilità di dover aspettare multipli di
k prima di poter ricostruire un pacchetto.\\
Un altro problema dell'ideal soliton consisteva nel fatto che spesso non si
riusciva a decodificare perchè alcuni pacchetti non stavano in nessuna
componente, si rimedia creando delle componenti formate da tanti pacchetti.\\
%Inserisci grafico dagli articoli.
In questo modo si ha un overhead medio del 5\%, ma in questo caso quello che si
ottiene è diverso da un Linear Fountain Code.
\section {Raptor Code}
I {\bf Raptor Code} sono tra i più utilizzati nel campo delle comunicazioni per
effettuare comunicazione di tipo broadcast e nel caso di canali di comunicazione
con alta latenza (per esempio comunicazioni satelittari).\\
Lo scopo dei  Raptor Code è di ridurre la complessità di codifica e decodifica a
una complessità linerare O(k), complessità che risulta essere utile solo con
valori di K molto elevati.\\
Un codice Raptor diminusice la possibilità di decodificare il messaggio, questo
è dovuto al fatto che viene posto un limite superiore alla distribuzione di
probabilità e viene introdotto un secondo codice di ridondanza basato sui Campi
di Galois per coprire una perdita dei dati pari al 5\%, che sommato al 95\% che
viene garantita dai codici Raptor si riesce quindi a decodificare il messaggio.